import java.util.*;

/**
 * 面试题 16.24. 数对和
 * https://leetcode-cn.com/problems/pairs-with-sum-lcci/
 */
public class Solutions_mianshi_16_24 {
    public static void main(String[] args) {
//        int[] nums = {5, 6, 5};
//        int target = 11;  // output: {{5, 6}}

        int[] nums = {5, 6, 3, -6, 2, 1, 1, 0, 8, 0};
        int target = 2;  // output: {{-6, 8}, {0, 2}, {1, 1}}

//        int[] nums = {5, 6, 5, 6};
//        int target = 11;  // output: {{5, 6}, {5, 6}}

//        int[] nums = {-2, -1, 0, 3, 5, 6, 7, 9, 13, 14};
//        int target = 12;  // output: {{-2, 14}, {-1, 13}, {3, 9}, {5, 7}}

        List<List<Integer>> result = pairSums(nums, target);
        System.out.println(result);
    }

    /**
     * 解法二：排序 + 双指针（28ms）
     */
    public static List<List<Integer>> pairSums(int[] nums, int target) {
        // nums 中全部元素加入到 map 中
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 1) {
            return res;
        }
        Arrays.sort(nums);
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                res.add(Arrays.asList(nums[left], nums[right]));
                left ++;
                right --;
            } else if (sum < target) {
                // 左指针右移，sum 值将更大
                left ++;
            } else if (sum > target) {
                // 右指针左移，sum 值将更小
                right --;
            }
        }
        return res;
    }

    /**
     * 解法一：哈希表（43ms）
     */
    public static List<List<Integer>> pairSums2(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 2) {
            return res;
        }
        // key：数，value：在 nums 中出现的次数
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            // 获取 target - num 的出现次数
            int count = map.getOrDefault(target - num, 0);
            if (count > 0) {
                res.add(Arrays.asList(target - num, num));
                // 匹配一次后，target - num 可使用次数减 1
                map.put(target - num, count - 1);
            } else {
                // 未匹配到，则 num 记录到 map 中
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
        }
        return res;
    }
}
